Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees
Identifieur interne : 000087 ( Istex/Curation ); précédent : 000086; suivant : 000088Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees
Auteurs : Cohen ; Fraigniaud ; MitjanaSource :
- Theory of Computing Systems [ 1432-4350 ] ; 2002-12-01.
Abstract
Abstract: This paper addresses the minimum-time broadcast problem under several modes of the line model, i.e., when long-distance calls can be placed along paths in the network. It is well known that the minimum-time broadcast problem can be solved in polynomial time under the single-port edge-disjoint paths mode. However, it is equally well known that either relaxing the model to the all-port edge-disjoint paths mode, or constraining the model to the single-port vertex-disjoint paths mode, leads to NP-complete problems; and exact solutions have been derived for specific topologies only (e.g., hypercubes or tori). In this paper we present polynomial-time algorithms for minimum-time broadcast in trees. These algorithms are obtained by application of an original technique called the merging method , which can be applied in a larger context, for instance, to solve the multicast problem or to address the restricted regimen. The merging method requires solving the minimal contention-free matrix problem whose solution presents some interest on its own.
Url:
DOI: 10.1007/s00224-002-1047-5
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000087
Links to Exploration step
ISTEX:045EFDF67DBE8743E2C63CA58359EAC90B8CCDA5Curation
No country items
Cohen<affiliation><mods:affiliation>LORIA, Université Nancy, 54003 Nancy cedex, France Johanne.Cohen@loria.fr, FR</mods:affiliation><wicri:noCountry code="subField">FR</wicri:noCountry></affiliation><affiliation><mods:affiliation>LRI-CNRS, bât. 490, Université Paris-Sud, 91405 Orsay cedex, France Pierre.Fraigniaud@lri.fr, FR</mods:affiliation><wicri:noCountry code="subField">FR</wicri:noCountry></affiliation><affiliation><mods:affiliation>Departamento Matemàtica Aplicada, Universidad Politècnica de Catalunya, Barcelona, Spain margarida@ma1.upc.es, ES</mods:affiliation><wicri:noCountry code="subField">ES</wicri:noCountry></affiliation>Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees</title><author><name sortKey="Cohen" sort="Cohen" uniqKey="Cohen" first="" last="Cohen">Cohen</name><affiliation><mods:affiliation>LORIA, Université Nancy, 54003 Nancy cedex, France Johanne.Cohen@loria.fr, FR</mods:affiliation><wicri:noCountry code="subField">FR</wicri:noCountry></affiliation></author><author><name sortKey="Fraigniaud" sort="Fraigniaud" uniqKey="Fraigniaud" first="" last="Fraigniaud">Fraigniaud</name><affiliation><mods:affiliation>LRI-CNRS, bât. 490, Université Paris-Sud, 91405 Orsay cedex, France Pierre.Fraigniaud@lri.fr, FR</mods:affiliation><wicri:noCountry code="subField">FR</wicri:noCountry></affiliation></author><author><name sortKey="Mitjana" sort="Mitjana" uniqKey="Mitjana" first="" last="Mitjana">Mitjana</name><affiliation><mods:affiliation>Departamento Matemàtica Aplicada, Universidad Politècnica de Catalunya, Barcelona, Spain margarida@ma1.upc.es, ES</mods:affiliation><wicri:noCountry code="subField">ES</wicri:noCountry></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:045EFDF67DBE8743E2C63CA58359EAC90B8CCDA5</idno><date when="2002" year="2002">2002</date><idno type="doi">10.1007/s00224-002-1047-5</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-61X6212W-J/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000087</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000087</idno><idno type="wicri:Area/Istex/Curation">000087</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees</title><author><name sortKey="Cohen" sort="Cohen" uniqKey="Cohen" first="" last="Cohen">Cohen</name><affiliation><mods:affiliation>LORIA, Université Nancy, 54003 Nancy cedex, France Johanne.Cohen@loria.fr, FR</mods:affiliation><wicri:noCountry code="subField">FR</wicri:noCountry></affiliation></author><author><name sortKey="Fraigniaud" sort="Fraigniaud" uniqKey="Fraigniaud" first="" last="Fraigniaud">Fraigniaud</name><affiliation><mods:affiliation>LRI-CNRS, bât. 490, Université Paris-Sud, 91405 Orsay cedex, France Pierre.Fraigniaud@lri.fr, FR</mods:affiliation><wicri:noCountry code="subField">FR</wicri:noCountry></affiliation></author><author><name sortKey="Mitjana" sort="Mitjana" uniqKey="Mitjana" first="" last="Mitjana">Mitjana</name><affiliation><mods:affiliation>Departamento Matemàtica Aplicada, Universidad Politècnica de Catalunya, Barcelona, Spain margarida@ma1.upc.es, ES</mods:affiliation><wicri:noCountry code="subField">ES</wicri:noCountry></affiliation></author></analytic><monogr></monogr><series><title level="j">Theory of Computing Systems</title><title level="j" type="abbrev">Theory Comput. Systems</title><idno type="ISSN">1432-4350</idno><idno type="eISSN">1433-0490</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><date type="published" when="2002-12-01">2002-12-01</date><biblScope unit="volume">35</biblScope><biblScope unit="issue">6</biblScope><biblScope unit="page" from="641">641</biblScope><biblScope unit="page" to="665">665</biblScope></imprint><idno type="ISSN">1432-4350</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">1432-4350</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: This paper addresses the minimum-time broadcast problem under several modes of the line model, i.e., when long-distance calls can be placed along paths in the network. It is well known that the minimum-time broadcast problem can be solved in polynomial time under the single-port edge-disjoint paths mode. However, it is equally well known that either relaxing the model to the all-port edge-disjoint paths mode, or constraining the model to the single-port vertex-disjoint paths mode, leads to NP-complete problems; and exact solutions have been derived for specific topologies only (e.g., hypercubes or tori). In this paper we present polynomial-time algorithms for minimum-time broadcast in trees. These algorithms are obtained by application of an original technique called the merging method , which can be applied in a larger context, for instance, to solve the multicast problem or to address the restricted regimen. The merging method requires solving the minimal contention-free matrix problem whose solution presents some interest on its own.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000087 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 000087 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:045EFDF67DBE8743E2C63CA58359EAC90B8CCDA5
|texte= Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees
}}
| This area was generated with Dilib version V0.6.33. |  |